#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<time.h>
#include<stdlib.h>
//插入排序函数
void InsertSort(int* arr, int N)
{
	for (int i = 0; i < N - 1; i++)
	{
		int end = i;
		//即将排序的元素，保留在tmp
		int tmp = arr[end + 1];
		//end>=0代表还有元素未比较
		while (end >= 0)
		{
			if (tmp < arr[end])
			{
				arr[end + 1] = arr[end];
				end--;
			}
			else
			{
				break;
			}
		}
		//来到这里分为两种情况 
		//1：break->遇到比元素tmp小或和tmp相等的，将m放在它的后面
		//2：全部比较完了，都没有遇到<=tmp的，最后tmp放在数组第一个位置
		arr[end + 1] = tmp;
	}

}
//希尔排序
//单for（多组并排）
void ShellSort(int* arr, int N)
{
	//gap初识为N，元素的个数
	int gap = N;
	//gap不为1就要继续的缩小并排序
	while (gap > 1)
	{
		//gap缩小
		gap = gap / 2;
		//也会有gap = gap/3 +1 的写法 这是针对元素更多的数组，+1会确保有一次gap为等于1
		for (int i = 0; i < N - gap; i++)
		{
			int end = i;
			//即将排序的元素，保留在tmp
			int tmp = arr[end + gap];
			//end>=0代表还有元素未比较
			while (end >= 0)
			{
				if (tmp < arr[end])
				{
					arr[end + gap] = arr[end];
					end -= gap;
				}
				else
				{
					break;
				}
				//来到这里分为两种情况 
					//1：break->遇到比元素tmp小或和tmp相等的，将m放在它的后面
					//2：全部比较完了，都没有遇到<=tmp的，最后tmp放在数组第一个位置
				arr[end + gap] = tmp;
			}
		}
	}
}
//希尔排序的第一种写法
//双for（一组排完，再排另外一组）
void ShellSort2(int* arr, int N)
{
	//gap初识为N，元素的个数
	int gap = N;
	//gap不为1就要继续的缩小并排序
	while (gap > 1)
	{
		//gap缩小
		gap = gap / 2;
		//同上也会也gap = gap/3 +1 的写法
		//这个for控制每组的元素
		for (int j = 0; j < gap; j++)
		{	//这个for控制每组内的排序
			for (int i = j; i < N - gap; i += gap)
			{
				int end = i;
				//即将排序的元素，保留在tmp
				int tmp = arr[end + gap];
				//end>=0代表还有元素未比较
				while (end >= 0)
				{
					if (tmp < arr[end])
					{
						arr[end + gap] = arr[end];
						end -= gap;
					}
					else
					{
						break;
					}
					//来到这里分为两种情况 
					//1：break->遇到比元素tmp小或和tmp相等的，将m放在它的后面
					//2：全部比较完了，都没有遇到<=tmp的，最后tmp放在数组第一个位置
					arr[end + gap] = tmp;
				}
			}
		}
	}
}
//主函数
int main()
{
	srand(time(0));
	const int N = 10000000;
	//三个开辟的数组空间，来进行对比插入和两种希尔的差距
	int* a1 = (int*)malloc(sizeof(int) * N);
	int* a2 = (int*)malloc(sizeof(int) * N);
	int* a3 = (int*)malloc(sizeof(int) * N);

	for (int i = N - 1; i >= 0; --i)
	{
		a1[i] = rand();
		a2[i] = a1[i];
		a3[i] = a1[i];
	}

	int begin1 = clock();
	//InsertSort(a1, N);
	int end1 = clock();

	int begin2 = clock();
	ShellSort(a2, N);
	int end2 = clock();

	int begin3 = clock();
	ShellSort2(a3, N);
	int end3 = clock();

	printf("InsertSort:%d\n", end1 - begin1);
	printf("ShellSort:%d\n", end2 - begin2);
	printf("ShellSorts:%d\n", end3 - begin3);

	free(a1);
	free(a2);
	free(a3);

	return 0;
}